package com.bo.day20240925;

/**
 * 判断是否平衡二叉树
 * 定义：树中任意节点的左右子树的高度差不超过1
 * 思路：
 * 1.递归判断左右子树是否平衡，同时返回高度
 * 2.如果左右子树有一个不平衡，返回false，不是平衡二叉树
 * 3.如果左右子树高度差超过1,返回false,不是平衡二叉树
 * 图解：https://cloud.fynote.com/share/d/IlaHZRAAK
 * @Author: gpb
 * @Date: 2024/9/25 16:06
 * @Description:
 */
public class IsBalanced {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node (int data) {
            this.value = data;
        }
    }

    public static class Info {
        public boolean isBalanced;
        public int height;

        public Info (boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    public static boolean isBalanced (Node head) {
        return process(head).isBalanced;
    }

    public static Info process (Node head) {
        // 递归终止条件,空树,是平衡二叉树，高度为0
        if (head == null) {
            return new Info(true, 0);
        }
        // 递归左树,获取左树信息,是否是平衡二叉树，左树的高度
        Info leftInfo = process(head.left);
        // 递归右树,获取右树信息,是否是平衡二叉树，右树的高度
        Info rightInfo = process(head.right);
        // 计算当前树的高度
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        // 是否是平衡二叉树
        boolean isBalanced = true;
        // 如果左右子树有一个不平衡，返回false，不是平衡二叉树
        if (!leftInfo.isBalanced || !rightInfo.isBalanced) {
            isBalanced = false;
        }
        // 如果左右子树高度差超过1,返回false,不是平衡二叉树
        if (Math.abs(leftInfo.height - rightInfo.height) > 1) {
            isBalanced = false;
        }
        return new Info(isBalanced, height);
    }
}
